package com.skh.binaryTree;

/**
 * @Author: skh
 * @Date: 2020/3/20 10:18
 * @Description: 将有序数组转换为二叉搜索树
 */
public class SortedArrayToBST {
    /**
     * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
     * <p>
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     * <p>
     * 示例:
     * <p>
     * 给定有序数组: [-10,-3,0,5,9],
     * <p>
     * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
     * <p>
     * 0
     * / \
     * -3   9
     * /   /
     * -10  5
     */


    public TreeNode sortedArrayToBST(int[] nums) {

        return helper(nums,0,nums.length-1);
    }

    public TreeNode helper(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        //找出中间节点
        int p = (start + end) / 2;
        TreeNode root = new TreeNode(nums[p]);
        root.left = helper(nums, start, p - 1);
        root.right = helper(nums, p + 1, end);

        return root;

    }

}
